#include <vector>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>

using namespace std;

// 有序数组中是否存在一个数字

// 生成随机数组
vector<int> randomArray(int n, int v)
{
    vector<int> arr(n);
    for(int i = 0; i < n; ++i)
    {
        arr[i] = rand() % v + 1;
    }
    return arr;
}

// 为了验证
// 保证 arr 有序，才能用这个方法
bool right(vector<int>& arr, int num)
{
    for(int x : arr)
    {
        if(x == num) return true;
    }
    return false;
}

// 保证 arr 有序，才能用这个方法
bool exist(vector<int>& arr, int num)
{
    if(!arr.empty()) return false;

    int l = 0, r = arr.size() - 1, m = 0;
    while(l <= r)
    {
        m = (l + r) / 2;
        if(arr[m] == num) return true;
        else if(arr[m] > num) r = m - 1;
        else l = m + 1;
    }
    return false;
}

int main()
{
    srand(time(nullptr));
    int N = 100;
    int V = 1000;
    int testTime = 500000;
    cout << "测试开始" << endl;
    for(int i = 0; i < testTime; ++i)
    {
        int n = rand() % N;
        vector<int>&& arr = randomArray(n, V);
        sort(arr.begin(), arr.end());
        int num = rand() % V;
        if(right(arr, num) != exist(arr, num))
        {
            cout << "出错了!" << endl;
        }
    }
    cout << "测试结束" << endl;
    return 0;
}